package me.timlong.search;

public class WordSearch {

/*********************************************************************
 * 注意点：不要直接返回函数调用后的结果，最好使用if语句进行一个判断后再进行相关的处理，
 * 否则很容易出现逻辑错误
 *********************************************************************/

    /**
     * 题目描述
     * 给出一个二维字符数组和一个单词，判断单词是否在数组中出现，
     * 单词由相邻单元格的字母连接而成，相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。
     * 例如：
     * 给出的字符数组=
     * [↵
     *     ["ABCE"],↵
     *     ["SFCS"],↵
     *     ["ADEE"]↵
     * ]
     * 单词 ="ABCCED", -> 返回 true,
     * 单词 ="SEE", ->返回 true,
     * 单词 ="ABCB", -> 返回 false.
     *
     * 解决方案:
     * 使用深度优先遍历算法进行
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;

        int wordIndex = 0; //每次dfs，从word的首个字母开始进行对比


        // 遍历board
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean visited[][] = new boolean[rows][cols];  // 注意每次visited在以每个board[i][j]为root时，需要重新初始化，IMPORTANT，默认初始化为false
                if(dfs(board, i, j, word, wordIndex, visited))
                    return  true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, String word, int wordIndex, boolean[][] visited) {

        if(wordIndex >= word.length())
            return true;

        int rows = board.length;
        int cols = board[0].length;

        char[] wordChars = word.toCharArray();

        if(i >= 0 & i < rows && j >= 0 && j < cols && !visited[i][j] && board[i][j] == wordChars[wordIndex]){
            wordIndex++;
            visited[i][j] = true;
            if(dfs(board, i + 1, j, word, wordIndex, visited) || dfs(board, i - 1, j, word, wordIndex, visited) ||
                    dfs(board, i, j + 1, word, wordIndex, visited) || dfs(board, i, j - 1, word, wordIndex, visited))
                return true;

            visited[i][j] = false;
            //  if判断中采用||进行判断，当前面的相邻节点不能顺利匹配完整后，需要将该字符设置为visited=false
            //  否则，影响其他相邻节点的匹配过程，因此这个节点是关键

        }
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'C','A','A'},
                {'A','A','A'},
                {'B','C','D'}};
        String word = "ACDAB";
        System.out.println(new WordSearch().exist(board, word));

        // 不再dfs中添加visited【i】【j】 = fasle,下面的这个用力通不过
        char[][] strs = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}};

//                "ABCE","SFES","ADEE"};
        String word2 = "ABCESEEESF";
        System.out.println(new WordSearch().exist(strs, word2));

    }
}
